class Node {
    constructor(obj, dimension, parent = null) {
        this.obj = obj;
        this.left = null;
        this.right = null;
        this.parent = parent;
        this.dimension = dimension;
    }
}

let _maxDistance

export class KDTree {
    /**
     * @param points 需要进行大量计算的数据集合 [] 
     * @param metric 权重计算函数  例如 ： (a,b)=>{ return a.x+b.x }
     * @param dimensions 维度数组  例如 ： [ "x","y" ] |  ["x","z"]  ( key in T )
     */
    constructor(points, metric, dimensions) {

        this.dimensions = dimensions;
        this.points = points;
        this.metric = metric;

        function buildTree(points, depth, parent) {
            const dim = depth % dimensions.length;
            let median, node;

            if (points.length === 0) {
                return null;
            }
            if (points.length === 1) {
                return new Node(points[0], dim, parent);
            }

            points.sort(function (a, b) {
                return a[dimensions[dim]] - b[dimensions[dim]];
            });

            median = Math.floor(points.length / 2);
            node = new Node(points[median], dim, parent);
            node.left = buildTree(points.slice(0, median), depth + 1, node);
            node.right = buildTree(points.slice(median + 1), depth + 1, node);

            return node;
        }

        this.root = buildTree(points, 0, null);
    }

    /**
     * 最近邻查找
     * @param point 以 point 为目标，查找距离 point 最近的数据 
     * @param maxNodes 以 point 为目标，//查询最近的*计数*邻居到一个点
     * @param maxDistance 以 point 为目标，经过 metric 权重计算函数，距离 point 在 maxDistance 以内的数据
     * @returns [T,distance][] 返回二维数组，T 为数据，distance 为当前数据距离 point 的距离
     */
    nearest(point, maxNodes, maxDistance) {
        _maxDistance = maxDistance
        const scope = this;
        let result, bestNodes;

        // e[1] 为节点之间距离， 距离越大，值越小，在二进制堆中index越靠前
        bestNodes = new BinaryHeap(function (e) {
            return -e[1];
        });

        function nearestSearch(node) {
            const dimension = scope.dimensions[node.dimension];
            const ownDistance = scope.metric(point, node.obj);
            const linearPoint = {};

            let bestChild, linearDistance, otherChild;

            function saveNode(node, distance) {
                bestNodes.push([node, distance]);
                if (bestNodes.size() > maxNodes) {
                    bestNodes.pop();
                }
            }

            for (let i = 0; i < scope.dimensions.length; i += 1) {
                if (i === node.dimension) {
                    linearPoint[scope.dimensions[i]] = point[scope.dimensions[i]];
                } else {
                    linearPoint[scope.dimensions[i]] = node.obj[scope.dimensions[i]];
                }
            }

            linearDistance = scope.metric(linearPoint, node.obj);

            if (node.right === null && node.left === null) {
                if (bestNodes.size() < maxNodes || ownDistance <= bestNodes.peek()[1]) {
                    saveNode(node, ownDistance);
                }
                return;
            }

            if (node.right === null) {
                bestChild = node.left;
            } else if (node.left === null) {
                bestChild = node.right;
            } else {
                if (point[dimension] < node.obj[dimension]) {
                    bestChild = node.left;
                } else {
                    bestChild = node.right;
                }
            }

            nearestSearch(bestChild);

            if (bestNodes.size() < maxNodes || ownDistance <= bestNodes.peek()[1]) {
                saveNode(node, ownDistance);
            }

            if (bestNodes.size() < maxNodes || Math.abs(linearDistance) < bestNodes.peek()[1]) {
                if (bestChild === node.left) {
                    otherChild = node.right;
                } else {
                    otherChild = node.left;
                }
                if (otherChild !== null) {
                    nearestSearch(otherChild);
                }
            }
        }

        if (maxDistance) {
            for (let i = 0; i < maxNodes; i += 1) {
                bestNodes.push([null, maxDistance]);
            }
        }

        if (scope.root) nearestSearch(scope.root);

        result = [];

        for (let i = 0; i < Math.min(maxNodes, bestNodes.content.length); i += 1) {
            if (bestNodes.content[i][0]) {
                result.push([bestNodes.content[i][0].obj, bestNodes.content[i][1]]);
            }
        }
        return result;
    };
    remove(point) {

        const scope = this;
        const dimensions = scope.dimensions
        let node;

        function nodeSearch(node) {
            if (node === null) {
                return null;
            }

            let isEqual = true
            for (let i = 0; i < dimensions.length; i++) {
                const dimension = dimensions[i]
                if (node.obj[dimension] != point[dimension]) {
                    isEqual = false
                    break
                }
            }

            if (isEqual === true) {
                console.log("find");
                return node
            }

            var dimension = dimensions[node.dimension];

            if (point[dimension] < node.obj[dimension]) {
                return nodeSearch(node.left);
            } else if (point[dimension] > node.obj[dimension]) {
                return nodeSearch(node.right);
            } else {
                return nodeSearch(node.right) || nodeSearch(node.left);
            }
        }

        function removeNode(node) {
            let nextNode, nextObj, pDimension;

            function findMin(node, dim) {
                let dimension, own, left, right, min;

                if (node === null) {
                    return null;
                }

                dimension = dimensions[dim];

                if (node.dimension === dim) {
                    if (node.left !== null) {
                        return findMin(node.left, dim);
                    }
                    return node;
                }

                own = node.obj[dimension];
                left = findMin(node.left, dim);
                right = findMin(node.right, dim);
                min = node;

                if (left !== null && left.obj[dimension] < own) {
                    min = left;
                }
                if (right !== null && right.obj[dimension] < min.obj[dimension]) {
                    min = right;
                }
                return min;
            }

            if (node.left === null && node.right === null) {
                if (node.parent === null) {
                    scope.root = null;
                    return;
                }

                pDimension = dimensions[node.parent.dimension];

                if (node.obj[pDimension] < node.parent.obj[pDimension]) {
                    node.parent.left = null;
                } else {
                    node.parent.right = null;
                }
                return;
            }

            // 如果右子树不为空，使用节点维度上最小的元素进行替换，如果为空，交换左右子树，做同样的操作，保证节点再移除之后，原有树的顺序依旧保持
            if (node.right !== null) {
                nextNode = findMin(node.right, node.dimension);
                nextObj = nextNode.obj;
                removeNode(nextNode);
                node.obj = nextObj;
            } else {
                nextNode = findMin(node.left, node.dimension);
                nextObj = nextNode.obj;
                removeNode(nextNode);
                node.right = node.left;
                node.left = null;
                node.obj = nextObj;
            }
        }

        node = nodeSearch(scope.root);
        if (node === null) {
            return;
        }

        removeNode(node);

    };
    balanceFactor() {
        function height(node) {
            if (node === null) {
                return 0;
            }
            return Math.max(height(node.left), height(node.right)) + 1;
        }

        function count(node) {
            if (node === null) {
                return 0;
            }
            return count(node.left) + count(node.right) + 1;
        }

        return height(this.root) / (Math.log(count(this.root)) / Math.log(2));
    };
    insert(point) {
        const scope = this;
        function innerSearch(node, parent) {
            if (node === null) {
                return parent;
            }

            const dimension = scope.dimensions[node.dimension];
            if (point[dimension] < node.obj[dimension]) {
                return innerSearch(node.left, node);
            } else {
                return innerSearch(node.right, node);
            }
        }

        const insertPosition = innerSearch(this.root, null);
        let newNode, dimension;

        if (insertPosition === null) {
            this.root = new Node(point, null, null);
            return;
        }

        newNode = new Node(point, (insertPosition.dimension + 1) % this.dimensions.length, insertPosition);
        dimension = this.dimensions[insertPosition.dimension];

        if (point[dimension] < insertPosition.obj[dimension]) {
            insertPosition.left = newNode;
        } else {
            insertPosition.right = newNode;
        }
    };
    toJSON(src) {
        if (!src) src = this.root;
        const dest = new Node(src.obj, src.dimension, null);
        if (src.left) dest.left = this.toJSON(src.left);
        if (src.right) dest.right = this.toJSON(src.right);
        return dest;
    };
}

// 使用二进制堆存储数据
class BinaryHeap {
    content;
    scoreFunction;
    constructor(scoreFunction) {
        this.content = [];
        this.scoreFunction = scoreFunction;
    }
    push(element) {
        this.content.push(element);
        this.bubbleUp(this.content.length - 1);
    }
    pop() {
        let result = this.content[0];

        if (result[0] !== null && result[1] === _maxDistance) {
            let temp = -1
            for (let i = 0; i < this.content.length; i++) {
                if (this.content[i][0] === null) {
                    temp = i
                    break
                }
            }

            if (temp !== -1) {
                result = this.content[temp]
                this.content.splice(temp, 1)
                this.content.unshift(result)
            }
        }



        const end = this.content.pop();
        if (this.content.length > 0) {
            this.content[0] = end;
            this.sinkDown(0);
        }
        return result;
    }
    peek() {
        return this.content[0];
    }
    remove(node) {
        const len = this.content.length;
        for (let i = 0; i < len; i++) {
            if (this.content[i] == node) {
                const end = this.content.pop();
                if (i != len - 1) {
                    this.content[i] = end;
                    if (this.scoreFunction(end) < this.scoreFunction(node)) this.bubbleUp(i);
                    else this.sinkDown(i);
                }
                return;
            }
        }
        throw new Error("Node not found.");
    }
    size() {
        return this.content.length;
    }

    // 向上冒泡
    bubbleUp(n) {
        const element = this.content[n];
        while (n > 0) {
            const parentN = Math.floor((n + 1) / 2) - 1;
            const parent = this.content[parentN];
            if (this.scoreFunction(element) < this.scoreFunction(parent)) {
                this.content[parentN] = element;
                this.content[n] = parent;
                n = parentN;
            } else {
                break;
            }
        }
    }

    // 向下沉
    sinkDown(n) {

        const length = this.content.length;
        const element = this.content[n];
        const elemScore = this.scoreFunction(element);

        while (true) {
            const child2N = (n + 1) * 2;
            const child1N = child2N - 1;
            let swap = null;
            let child1Score;
            if (child1N < length) {
                const child1 = this.content[child1N];
                child1Score = this.scoreFunction(child1);

                if (child1Score <= elemScore) swap = child1N;
            }

            if (child2N < length) {
                const child2 = this.content[child2N];
                const child2Score = this.scoreFunction(child2);
                if (child2Score < (swap == null ? elemScore : child1Score)) {
                    swap = child2N;
                }
            }

            if (swap != null) {
                this.content[n] = this.content[swap];
                this.content[swap] = element;
                n = swap;
            } else {
                break;
            }
        }
    }
}


